import java.util.LinkedList;
import java.util.Queue;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 17655
 * Date: 2025-02-27
 * Time: 11:18
 */
public class test1 {
    /**
     * LeetCode 1926  迷宫中离入口最近的出口
     */


    int[] dx = {0,0,-1,1};
    int[] dy = {1,-1,0,0};

    public int nearestExit(char[][] maze, int[] e) {
        int m = maze.length;
        int n = maze[0].length;
        boolean[][] vis = new boolean[m][n];
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{e[0],e[1]});
        vis[e[0]][e[1]] = true;

        // 记录步数
        int step = 0;
        while(!q.isEmpty()){
            step++;
            int size = q.size();
            for(int i=0;i<size;i++){
                int[] t = q.poll();
                int a = t[0];
                int b = t[1];
                for(int j=0;j<4;j++){
                    int x = a+dx[j];
                    int y = b+dy[j];
                    if(x>=0 && x<m && y>=0 && y<n && maze[x][y]=='.' && !vis[x][y]){
                        // 是否已经走到出口
                        if(x==0 || x==m-1 || y==0 || y==n-1){
                            return step;
                        }else {
                            q.add(new int[]{x,y});
                            vis[x][y] = true;
                        }
                    }
                }
            }
        }
        return -1;
    }
}
